/**
 * 5. Longest Palindromic Substring 最长回文子串
 * https://leetcode-cn.com/problems/longest-palindromic-substring/
 */
class LongestPalindromicSubstring {
    /**
     * 方法：动态规划求解最长回文子串
     *      dp[i][j]表示s[i:j+1]是否为回文串
     *      状态转移方程：dp[i][j] = (s[i] == s[j]) and dp[i+1][j-1]
     *      边界条件：
     *      - 单个字符是回文串 dp[i][i] = true
     *      - 两个相同字符是回文串 dp[i][i+1] = true if s[i] == s[i+1]
     *
     * Args:
     *      s: String - 输入字符串
     *
     * Returns:
     *      String: 返回最长回文子串
     *
     * Time: O(n^2) - n为字符串长度,需要填充n^2大小的dp表
     *
     * Space: O(n^2) - 需要n^2大小的dp表存储状态
     */
    public String longestPalindrome(String s) {
        int n = s.length();
        if(n < 2){
            return s;
        }
        boolean[][] dp = new boolean[n][n];
        char[] charArry = s.toCharArray();
        for(int i = 0; i < n; i++){
            dp[i][i] = true;
        }
        int maxLength = 1;    // 记录最长回文长度
        int start = 0;        // 记录最长回文的起始位置

        // 检查长度为2的子串
        for (int i = 0; i < n - 1; i++) {
            if (s.charAt(i) == s.charAt(i + 1)) {
                dp[i][i + 1] = true;
                start = i;
                maxLength = 2;
            }
        }
        // 检查长度大于2的子串
        for (int len = 3; len <= n; len++) {  // len表示子串长度
            for (int i = 0; i <= n - len; i++) {  // i表示子串起始位置
                int j = i + len - 1;  // j表示子串结束位置
                
                // 状态转移方程
                if (s.charAt(i) == s.charAt(j) && dp[i + 1][j - 1]) {
                    dp[i][j] = true;
                    
                    // 更新最长回文信息
                    if (len > maxLength) {
                        maxLength = len;
                        start = i;
                    }
                }
            }
        }
        return s.substring(start, start + maxLength);
    }

    /**
     * 方法：中心扩展法。从每个位置向两边扩展，找到以该位置为中心的最长回文串。
     * 需要考虑奇数长度(一个字符为中心)和偶数长度(两个字符为中心)两种情况。
     *
     * Args:
     *      s: String - 输入字符串
     *
     * Returns:
     *      String: 返回最长回文子串
     *
     * Time: O(n^2) - n为字符串长度,每个位置都需要向两边扩展,最坏情况下扩展n次
     *
     * Space: O(1) - 只使用常数额外空间
     */
    public static String longestPalindrome1(String s) {
        if (s == null || s.length() < 1) return "";

        int start = 0, end = 0;

        for (int i = 0; i < s.length(); i++) {
            // 奇数长度回文
            int len1 = expandAroundCenter(s, i, i);
            // 偶数长度回文
            int len2 = expandAroundCenter(s, i, i + 1);

            int len = Math.max(len1, len2);
            if (len > end - start) {
                start = i - (len - 1) / 2;
                end = i + len / 2;
            }
        }

        return s.substring(start, end + 1);
    }

    private static int expandAroundCenter(String s, int left, int right) {
        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            left--;
            right++;
        }
        return right - left - 1;
    }

    public static String longestPalindrome3(String s) {
        if(s == null || s.length() == 0){
            return "";
        }
        if(s.length() == 1){
            return s;
        }
        //预处理字符串
        String processed = preprocess(s);
        int n = processed.length();
        int[] p = new int[n];  //回文半径数组
        int center = 0, right = 0;
        int maxCenter = 0, maxLen = 0;
        for(int i = 0; i < n; i++){
            //利用对成性
            if(i < right){
                int mirror = 2 * center - i;
                p[i] = Math.min(p[mirror], right - i);
            }
            //尝试扩展回文
            int leftB = i - (1 + p[i]);
            int rightB = i + (1 + p[i]);
            while(leftB >= 0 && rightB < n && processed.charAt(leftB) == processed.charAt(rightB)){
                p[i]++;
                leftB--;
                rightB++;
            }
            //更新中心和有边界
            if(i + p[i] > right){
                center = i;
                right = i + p[i];
            }
            //更新最大回文
            if(p[i] > maxLen){
                maxCenter = i;
                maxLen= p[i];
            }
        }
        int start = (maxCenter - maxLen) / 2;
        return s.substring(start, start + maxLen);
    }

    private static String preprocess(String s){
        StringBuilder sb = new StringBuilder();
        sb.append("#");
        for(int i = 0; i < s.length(); i++){
            sb.append(s.charAt(i)).append("#");
        }
        return sb.toString();
    }
}